Repair Roads (Codesprint problem)
I was looking though the old codesprint problems and came across this one:
The country of Byteland contains of N cities and N – 1 bidirectional roads between them such that there is a path between any two cities. The roads in Byteland were built long ago and now they are in need of repair. You have been hired to repair all the roads. You intend to do this by dispatching robots on some of the roads. Each robot will repair the road he is currently on and then move to one of the adjacent unrepaired roads. After repairing that, he will move to another adjacent unrepaired road, repair that and so on.
Two roads are adjacent if they have the same city at one of their endpoints. For the process to be efficient, no two robots will can ever repair the same road, and no road can be visited twice. What is the least number of robots needed to accomplish the task?
The solution is described here. But it wasn’t so clear to me. I’d like to work through the problem to compilation, unfortunately I need to get hold of the paper he references. Anyway, I fundamentally understand the method now and thought I’d write up my notes so far:
1. The first step is to recognise that representation we want is the line graph of roads connecting towns. Paths on this graph represent valid transitions between edges. The problem is then to find a set of paths that visit each vertex once, and only once. Clearly if there is a Hamiltonian path, only one path is required. And only one robot is therefore required.
2. The second thing to recognise is that the number we are looking for is the minimal number of edges to add to allow a Hamiltonian path to exist. See here. Why is that? It’s because each edge we add to the graph to make it Hamiltonian connects a previously disconnected path. Each of those disconnected paths requires its own robot.
3. The next thing to recognise is that because there are N cities and N-1 edges, the graph is always a tree.
So we need to find a Hamiltonian completion of the line graph of a tree. And it turns out that there’s a linear time algorithm for doing this (though I’m unable to download the paper). This paper.
If I can dig out the paper (if you’re feeling kind and would like to help me get a copy, let me know) I might have a go at implementing the algorithm.
RSS